'''
https://leetcode.cn/problems/decode-ways/
'''
from functools import cache


class Solution:
    def numDecodings(self, s: str) -> int:
        n = len(s)

        @cache
        def f(i: int) -> int:
            if i == n: return 1
            if s[i] == '0': return 0  # 不能是0开头的
            ans = f(i + 1)
            if i + 1 < n and (int(s[i]) * 10 + int(s[i + 1])) < 27:
                ans += f(i + 2)
            return ans

        return f(0)

    def numDecodings2(self, s: str) -> int:
        n = len(s)
        dp = [0] * (n + 2)
        dp[-1] = dp[-2] = 1
        for i in range(n - 1, -1, -1):
            if s[i] == '0':
                continue  # 不能是0开头的
            ans = dp[i + 1]
            if i + 1 < n and (int(s[i]) * 10 + int(s[i + 1])) < 27:
                ans += dp[i + 2]
            dp[i] = ans
        return dp[0]

    # 不太重要的状态压缩，因为这题的数据量可以不用状态压缩
    def numDecodings3(self, s: str) -> int:
        n = len(s)
        a = b = 1
        for i in range(n - 1, -1, -1):
            if s[i] == '0':
                c = 0
            else:
                c = a
                if i + 1 < n and (int(s[i]) * 10 + int(s[i + 1])) < 27:
                    c += b
            a, b = b, c
        return a
